package leetcode_day._2022._202203._2131;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/30 23:08
 * 找到处理最多请求的服务器
 * 算法：堆 + 有序集合
 */
public class _30_1606 {

    static Integer N = 100010;
    static int[] CNT = new int[N];
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        Arrays.fill(CNT, 0);
        int max = 0, n = arrival.length;
        PriorityQueue<int[]> busy = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        TreeSet<Integer> free = new TreeSet<>();
        for (int i = 0; i < k; i++) free.add(i);
        for (int i = 0; i < n; i++) {
            int start = arrival[i], end = start + load[i];
            while (!busy.isEmpty() && busy.peek()[1] <= start) free.add(busy.poll()[0]);
            Integer cur = free.ceiling(i % k);
            if (cur == null) cur = free.ceiling(0);
            if (cur == null) continue;
            free.remove(cur);
            busy.add(new int[]{cur, end});
            max = Math.max(max, ++CNT[cur]);
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) if (CNT[i] == max) ans.add(i);
        return ans;
    }

}
